﻿using System.Collections.Generic;

namespace System.DataStructures
{
	/// <summary>
	/// An set where the items are ordered. 
	/// </summary>
	/// <remarks>
	/// In order to check for equality for non-primitive types you must make sure the type implements <see cref="IComparable{T}"/> otherwise
	/// the <see cref="OrderedSet{T}"/> cannot guarantee the set contains only unique objects.
	/// </remarks>
	/// <typeparam name="T">Type of OrderedSet.</typeparam>
	internal sealed class OrderedSet<T> : SetBase<T>
		where T : IComparable<T>
	{
		private readonly AvlTree<T> _storage;

		/// <summary>
		/// Initializes a new instance of the <see cref="OrderedSet{T}"/> class.
		/// </summary>
		public OrderedSet()
		{
			_storage = new AvlTree<T>();
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="OrderedSet{T}"/> class populating the <see cref="OrderedSet{T}"/> 
		/// with the items within the provided <see cref="IEnumerable{T}"/>.
		/// </summary>
		/// <remarks>
		/// <para>
		/// Call this constructor if assigning a values to the <see cref="OrderedSet{T}"/>.
		/// </para>
		/// <para>
		/// This method is an O(n) operation where n is the number of items in the <see cref="IEnumerable{T}"/>.
		/// </para>
		/// </remarks>
		/// <param name="values">Items to populate the set with.</param>
		public OrderedSet(IEnumerable<T> values)
			: this()
		{
			_storage = new AvlTree<T>();
			_storage.AddRangeUnique(values);
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="OrderedSet{T}"/> class that uses the specified <see cref="IComparer{T}"/>.
		/// </summary>
		/// <param name="comparer">The comparer to use in value comparisons.</param>
		public OrderedSet(IComparer<T> comparer)
		{
			_storage = new AvlTree<T>(comparer);
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="OrderedSet{T}"/> class that uses the specified comparison function.
		/// </summary>
		/// <param name="comparer">The comparer to use in value comparisons.</param>
		public OrderedSet(Func<T, T, int> comparer)
		{
			_storage = new AvlTree<T>(comparer);
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="OrderedSet{T}"/> class populating the <see cref="OrderedSet{T}"/> 
		/// with the items within the provided <see cref="IEnumerable{T}"/> that uses the specified <see cref="IComparer{T}"/>.
		/// </summary>
		/// <remarks>
		/// <para>
		/// Call this constructor if assigning a values to the <see cref="OrderedSet{T}"/>.
		/// </para>
		/// <para>
		/// This method is an O(n) operation where n is the number of items in the <see cref="IEnumerable{T}"/>.
		/// </para>
		/// </remarks>
		/// <param name="values">Items to populate the set with.</param>
		/// <param name="comparer">The comparer to use in value comparisons.</param>
		public OrderedSet(IEnumerable<T> values, IComparer<T> comparer)
		{
			_storage = new AvlTree<T>(comparer);
			_storage.AddRangeUnique(values);
		}

		/// <summary>
		/// Initializes a new instance of the <see cref="OrderedSet&lt;T&gt;"/> class.
		/// </summary>
		/// <param name="values">The values.</param>
		/// <param name="comparer">The comparer.</param>
		public OrderedSet(IEnumerable<T> values, Func<T, T, int> comparer)
		{
			_storage = new AvlTree<T>(comparer);
			_storage.AddRangeUnique(values);
		}

		/// <summary>
		/// Gets the count.
		/// </summary>
		/// <value>The count.</value>
		public override int Count
		{
			get { return _storage.Count; }
		}

		/// <summary>
		/// Adds an item to the <see cref="OrderedSet{T}"/>.
		/// </summary>
		/// <remarks>
		/// This is an O(log n) operation.
		/// </remarks>
		/// <param name="item">Item to add to the <see cref="OrderedSet{T}"/>.</param>
		public override bool Add(T item)
		{
			return _storage.AddUnique(item);
		}

		/// <summary>
		/// Clears all the items from the <see cref="OrderedSet{T}"/>.
		/// </summary>
		public override void Clear()
		{
			_storage.Clear();
		}

		public override ISetEx<T> CloneType(IEnumerable<T> initialContents = null)
		{
			return new OrderedSet<T>(initialContents);
		}

		public override bool Contains(T item)
		{
			return _storage.Contains(item);
		}

		public override IEnumerator<T> GetEnumerator()
		{
			return _storage.GetInorderEnumerator().GetEnumerator();
		}

		public override bool Remove(T item)
		{
			return _storage.Remove(item);
		}

		public T[] ToArray()
		{
			T[] local = new T[Count];
			int i = 0;
			foreach (T item in _storage.GetInorderEnumerator())
			{
				local[i++] = item;
			}
			return local;
		}
	}
}